18. Sequences

d1. Recursively Defined Sequences

Sometimes the terms of a sequence are not given explicitly. Rather they may be defined recursively in that each term is given in terms of one or more previous terms by a formula called a recursion (or recurrence) relation. In that case one must also specify one or more initial terms of the sequence.

Write out the first six terms of the sequence \(a_n\) satisfying the recursion relation \(a_{n+1}=\dfrac{1}{3}a_n+2\) if the initial term is \(a_1=6\).

\[\begin{aligned} a_1&=6 \\ a_2&=\dfrac{1}{3}a_1+2=\dfrac{1}{3}6+2=4 \\ a_3&=\dfrac{1}{3}a_2+2=\dfrac{1}{3}4+2=\dfrac{10}{3}\approx 3.333 \\ a_4&=\dfrac{1}{3}a_3+2=\dfrac{1}{3}\dfrac{10}{3}+2=\dfrac{28}{9}\approx 3.111 \\ a_5&=\dfrac{1}{3}a_4+2=\dfrac{1}{3}\dfrac{28}{9}+2=\dfrac{82}{27}\approx 3.037 \\ a_6&=\dfrac{1}{3}a_5+2=\dfrac{1}{3}\dfrac{82}{27}+2=\dfrac{244}{81}\approx 3.012 \end{aligned}\]

It is usually very difficult to find an explicit formula for the general term of a sequence specified by a recursion relation. However, in some cases it is possible:

Guess a formula for the general term \(a_n\) of the sequence in the previous example. (Optional: Then prove this formula is correct by using mathematical induction.)

We notice that (for \(n \ge 3\)) each denominator is a power of \(3\) and each numerator is \(1\) more than a power of \(3\). Expressing these powers in terms of the index gives \[ a_n=\dfrac{3^{n-1}+1}{3^{n-2}} \] at least for \(3 \le n \le 6\). We also check: \(a_1=\dfrac{3^0+1}{3^{-1}}=6\) and \(a_2=\dfrac{3^1+1}{3^0}=4\) So the formula \(a_n=\dfrac{3^{n-1}+1}{3^{n-2}}\) works for \(n=1,2,3,4,5,6\) and appears to work for all \(n\). However, this is not a proof. For that we use mathematical induction.

We assume the formula works for \(n=k\), i.e. \(a_k=\dfrac{3^{k-1}+1}{3^{k-2}}\) and prove it works for \(n=k+1\), i.e. \(a_{k+1}=\dfrac{3^k+1}{3^{k-1}}\).

To show this, we use the recursion relation and the assumption: \[\begin{aligned} a_{k+1}&=\dfrac{1}{3}a_k+2 =\dfrac{1}{3}\dfrac{3^{k-1}+1}{3^{k-2}}+2 \\ &=\dfrac{3^{k-1}+1}{3^{k-1}}+\dfrac{2\cdot3^{k-1}}{3^{k-1}} =\dfrac{3\cdot3^{k-1}+1}{3^{k-1}} \\ &=\dfrac{3^k+1}{3^{k-1}} \end{aligned}\] which is the desired result.

The most famous sequence is the

The Fibonacci sequence, \(F_n\), is given by a two term recursion relation and two initial conditions: \[ F_1=1 \qquad F_2=1 \qquad F_n=F_{n-1}+F_{n-2} \qquad \text{for} \quad n \ge 3 \] Each term is the sum of the two preceeding terms. The first \(10\) terms are: \[\begin{aligned} F_1=1, \quad F_2=1, \quad F_3=2, \quad F_4=3, \quad F_5=5, \\ F_6=8, \quad F_7=13 \quad F_8=21 \quad F_9=34 \quad F_{10}=55 \end{aligned}\] The Fibonacci sequence is useful in studying certain biological systems and in developing an efficient search procedure. You may want to read the Wikipedia article: Fibonacci Sequence

18. Sequences

d1. Recursively Defined Sequences

Heading